{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树任务调度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimalExecTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树任务调度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的。</p>\n",
    "\n",
    "<p>通常任务之间是存在依赖关系的，即对于某个任务，你需要先<strong>完成</strong>他的前导任务（如果非空），才能开始执行该任务。<strong>我们保证任务的依赖关系是一棵二叉树，</strong>其中 <code>root</code> 为根任务，<code>root.left</code> 和 <code>root.right</code> 为他的两个前导任务（可能为空），<code>root.val</code> 为其自身的执行时间。</p>\n",
    "\n",
    "<p>在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数。</p>\n",
    "\n",
    "<p>现在，系统有<strong>两个</strong> CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p><img alt=\"image.png\" src=\"https://pic.leetcode-cn.com/3522fbf8ce4ebb20b79019124eb9870109fdfe97fe9da99f6c20c07ceb1c60b3-image.png\" /></p>\n",
    "\n",
    "<p>输入：root = [47, 74, 31]</p>\n",
    "\n",
    "<p>输出：121</p>\n",
    "\n",
    "<p>解释：根节点的左右节点可以并行执行31分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是121分钟。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p><img alt=\"image.png\" src=\"https://pic.leetcode-cn.com/13accf172ee4a660d241e25901595d55b759380b090890a17e6e7bd51a143e3f-image.png\" /></p>\n",
    "\n",
    "<p>输入：root = [15, 21, null, 24, null, 27, 26]</p>\n",
    "\n",
    "<p>输出：87</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p><img alt=\"image.png\" src=\"https://pic.leetcode-cn.com/bef743a12591aafb9047dd95d335b8083dfa66e8fdedc63f50fd406b4a9d163a-image.png\" /></p>\n",
    "\n",
    "<p>输入：root = [1,3,2,null,null,4,4]</p>\n",
    "\n",
    "<p>输出：7.5</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= 节点数量 &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= 单节点执行时间 &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-shu-ren-wu-diao-du](https://leetcode.cn/problems/er-cha-shu-ren-wu-diao-du/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-shu-ren-wu-diao-du](https://leetcode.cn/problems/er-cha-shu-ren-wu-diao-du/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[47, 74, 31]', '[75,null,18,null,20,27,36]', '[1,3,2,null,null,4,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "\n",
    "        def dfs(root: TreeNode) -> tuple:\n",
    "            if not root:\n",
    "                return 0.0, 0.0\n",
    "            lf, rf = dfs(root.left), dfs(root.right)\n",
    "            return root.val + lf[0] + rf[0], max((lf[0] + rf[0]) / 2, lf[1], rf[1]) + root.val\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0, 0\n",
    "            a, b = dfs(node.left)\n",
    "            c, d = dfs(node.right)\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            total = node.val + a + c\n",
    "            if a - c <= 2*b:\n",
    "                parallel = (a+c)/2\n",
    "            else:\n",
    "                parallel = b + c\n",
    "            return total,  parallel\n",
    "        \n",
    "        t, p = dfs(root)\n",
    "        return t - p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0., 0.\n",
    "            tc = root.val\n",
    "\t\t\t\n",
    "            # 先递归左右子树\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "            \n",
    "            tc = tc + a + c\n",
    "            # 只考虑 a >= c 的情况，不满足就交换\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            \n",
    "            if a - 2 * b <= c:\n",
    "                pc = (a + c) / 2\n",
    "            else:\n",
    "                pc = c + b\n",
    "\n",
    "            return tc, pc\n",
    "\n",
    "        tc, pc = dfs(root)\n",
    "        return tc - pc\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        \n",
    "        def dfs(root: TreeNode) -> Tuple[float, float]:\n",
    "            if root is None:\n",
    "                return 0.0, 0.0\n",
    "\n",
    "            s1, t1 = dfs(root.left)\n",
    "            s2, t2 = dfs(root.right)\n",
    "\n",
    "            return s1 + s2 + root.val, max(max(t1, t2), (s1 + s2) / 2) + root.val\n",
    "\n",
    "        return dfs(root)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "\n",
    "        def dfs(root) -> List[float]:\n",
    "            if root is None:\n",
    "                return [0.0, 0.0]\n",
    "\n",
    "            tc = root.val\n",
    "\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "\n",
    "            tc += a + c\n",
    "\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            \n",
    "            if a - 2 * b <= c:\n",
    "                pc = (a + c) / 2\n",
    "            else:\n",
    "                pc = c + b\n",
    "\n",
    "            return [tc, pc]\n",
    "\n",
    "        tc, pc = dfs(root)\n",
    "\n",
    "        return tc - pc\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(rt):\n",
    "            if not rt: return 0,0\n",
    "            l = dfs(rt.left)\n",
    "            r = dfs(rt.right)\n",
    "            return max(l[0], r[0], (l[1]+r[1])/2)+rt.val, l[1]+r[1]+rt.val\n",
    "        return dfs(root)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            s1,t1 = dfs(root.left)\n",
    "            s2,t2 = dfs(root.right) \n",
    "            if s2 > s1 :\n",
    "                s1,t1,s2,t2 = s2,t2,s1,t1 \n",
    "            return s1+s2+root.val, max((s1+s2)/2, t1) + root.val\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0.0,0.0\n",
    "            s1,t1 = dfs(root.left)\n",
    "            s2,t2 = dfs(root.right)\n",
    "            return s1+s2+root.val,max(max(t1,t2),(s1+s2)/2)+root.val\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return [0.0,0.0]\n",
    "            lc = dfs(root.left)\n",
    "            rc = dfs(root.right)\n",
    "            print(lc)\n",
    "            print(rc)\n",
    "            v1 = (lc[0]+rc[0])/2\n",
    "            v2 = max(lc[1],rc[1])\n",
    "            return [root.val+lc[0]+rc[0],root.val+max(v1,v2)]\n",
    "        return min(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimalExecTime(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0., 0.\n",
    "            tc = root.val\n",
    "\t\t\t\n",
    "            # 先递归左右子树\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "            \n",
    "            tc = tc + a + c\n",
    "            # 只考虑 a >= c 的情况，不满足就交换\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            \n",
    "            if a - 2 * b <= c:\n",
    "                pc = (a + c) / 2\n",
    "            else:\n",
    "                pc = c + b\n",
    "\n",
    "            return tc, pc\n",
    "\n",
    "        tc, pc = dfs(root)\n",
    "        return tc - pc\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0 \n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            return max(l[0], r[0], (l[1] + r[1]) / 2) + node.val, l[1] + r[1] + node.val\n",
    "        return dfs(root)[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0,0\n",
    "            tc=root.val    \n",
    "            a,b=dfs(root.left)\n",
    "            c,d=dfs(root.right)\n",
    "            tc = tc+a+c    #总时间\n",
    "            if a<c:\n",
    "                a,c = c,a \n",
    "                b,d = d,b\n",
    "            if 2*b>=a-c :\n",
    "                pc=(a+c)/2\n",
    "            else:\n",
    "                pc=b+c\n",
    "            return tc,pc\n",
    "        \n",
    "        tc , pc = dfs(root)\n",
    "        return tc-pc\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution(object):\n",
    "    def minimalExecTime(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0., 0.\n",
    "            tc = root.val\n",
    "\t\t\t\n",
    "            # 先递归左右子树\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "            \n",
    "            tc = tc + a + c\n",
    "            # 只考虑 a >= c 的情况，不满足就交换\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            \n",
    "            if a - 2 * b <= c:\n",
    "                pc = (a + c) / 2\n",
    "            else:\n",
    "                pc = c + b\n",
    "\n",
    "            return tc, pc\n",
    "\n",
    "        tc, pc = dfs(root)\n",
    "        return tc - pc\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return [0.,0.]\n",
    "            s1,t1 = dfs(root.left)\n",
    "            s2,t2 = dfs(root.right)\n",
    "            if s1<s2:\n",
    "                s1,s2=s2,s1\n",
    "                t1,t2=t2,t1\n",
    "            return [s1+s2+root.val,max(t1,(s1+s2)/2)+root.val]\n",
    "        return dfs(root)[1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimalExecTime(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0., 0.\n",
    "            tc = root.val\n",
    "                        \n",
    "            # 先递归左右子树\n",
    "            a, b = dfs(root.left)\n",
    "            c, d = dfs(root.right)\n",
    "            \n",
    "            tc = tc + a + c\n",
    "            # 只考虑 a >= c 的情况，不满足就交换\n",
    "            if a < c:\n",
    "                a, c = c, a\n",
    "                b, d = d, b\n",
    "            \n",
    "            if a - 2 * b <= c:\n",
    "                pc = (a + c) / 2\n",
    "            else:\n",
    "                pc = c + b\n",
    "\n",
    "            return tc, pc\n",
    "\n",
    "        tc, pc = dfs(root)\n",
    "        return tc - pc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minimalExecTime(self, root: TreeNode) -> float:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0.,0.\n",
    "\n",
    "            x = root.val \n",
    "            a,b = dfs(root.left)\n",
    "            c,d = dfs(root.right)\n",
    "            x = c +a + x \n",
    "\n",
    "            if a <c:\n",
    "                a,c = c,a\n",
    "                b,d = d,b \n",
    "            if a-2*b <= c:\n",
    "                y = (a+c)/2 \n",
    "            else:\n",
    "                y = b+c \n",
    "\n",
    "            return x,y \n",
    "        x,y = dfs(root)\n",
    "\n",
    "        return x-y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "  def minimalExecTime(self, root: TreeNode) -> float:\n",
    "    def f(node):\n",
    "      if not node: return (0, 0)\n",
    "      s1, t1 = f(node.left)\n",
    "      s2, t2 = f(node.right)\n",
    "      return (s1 + s2 + node.val, max(t1, t2, (s1 + s2) / 2) + node.val)\n",
    "    return f(root)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
